While prime numbers are a central part of number theory and attract much attention, they do not appear to be critical for the analytic orientation of this website. For that reason this presentation is relegated to the diversions section: prime numbers are fun for play just like LEGOs!
Prime Number Sieve
Prime Factorization
Goldbach Pairs
Twin Primes
The ancient algorithm for locating all primes, which goes by the name of Eratosthenes, is surprisingly simple to code. It only requires these few lines:
var sieve = [];
function generateSieve( n ) {
sieve = [ false, false, true, true ];
for ( var i = 4 ; i <= n ; i += 2 ) sieve.push( false, true );
var max = Math.sqrt( sieve.length );
for ( var i = 3 ; i <= max ; i++ )
for ( var j = i*i ; j < sieve.length ; j += i ) sieve[j] = false;
}
The function generateSieve() updates the array sieve to indicate which integers less than or equal to the input argument are of the indicated type. The array is padded to allow direct indexing of integers, so that it is simple to implement a function to check whether a given number is prime:
function isPrime( n ) {
if ( typeof sieve[n] !== 'undefined' ) return sieve[n];
throw Error( 'Need to locate sufficient primes' );
}
With this simple apparatus one can easily generate a list of small(ish) primes:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
The first three lines can be compared to A000040 to confirm accuracy.
The main drawback to implementing primes in JavaScript is that the entire data set must remain in active memory, since there is no way to save data to disk without user interaction. Still, this works well enough to provide a decent playground for testing relationships.
The main reason for introducing the idea of primes is naturally for factoring composite numbers. With a list of primes in hand this is straightforward. The factorizations of integers up to one thousand are
2 = 2
3 = 3
4 = 22
5 = 5
6 = 2 × 3
7 = 7
8 = 23
9 = 32
10 = 2 × 5
11 = 11
12 = 22 × 3
13 = 13
14 = 2 × 7
15 = 3 × 5
16 = 24
17 = 17
18 = 2 × 32
19 = 19
20 = 22 × 5
21 = 3 × 7
22 = 2 × 11
23 = 23
24 = 23 × 3
25 = 52
26 = 2 × 13
27 = 33
28 = 22 × 7
29 = 29
30 = 2 × 3 × 5
31 = 31
32 = 25
33 = 3 × 11
34 = 2 × 17
35 = 5 × 7
36 = 22 × 32
37 = 37
38 = 2 × 19
39 = 3 × 13
40 = 23 × 5
41 = 41
42 = 2 × 3 × 7
43 = 43
44 = 22 × 11
45 = 32 × 5
46 = 2 × 23
47 = 47
48 = 24 × 3
49 = 72
50 = 2 × 52
51 = 3 × 17
52 = 22 × 13
53 = 53
54 = 2 × 33
55 = 5 × 11
56 = 23 × 7
57 = 3 × 19
58 = 2 × 29
59 = 59
60 = 22 × 3 × 5
61 = 61
62 = 2 × 31
63 = 32 × 7
64 = 26
65 = 5 × 13
66 = 2 × 3 × 11
67 = 67
68 = 22 × 17
69 = 3 × 23
70 = 2 × 5 × 7
71 = 71
72 = 23 × 32
73 = 73
74 = 2 × 37
75 = 3 × 52
76 = 22 × 19
77 = 7 × 11
78 = 2 × 3 × 13
79 = 79
80 = 24 × 5
81 = 34
82 = 2 × 41
83 = 83
84 = 22 × 3 × 7
85 = 5 × 17
86 = 2 × 43
87 = 3 × 29
88 = 23 × 11
89 = 89
90 = 2 × 32 × 5
91 = 7 × 13
92 = 22 × 23
93 = 3 × 31
94 = 2 × 47
95 = 5 × 19
96 = 25 × 3
97 = 97
98 = 2 × 72
99 = 32 × 11
100 = 22 × 52
101 = 101
102 = 2 × 3 × 17
103 = 103
104 = 23 × 13
105 = 3 × 5 × 7
106 = 2 × 53
107 = 107
108 = 22 × 33
109 = 109
110 = 2 × 5 × 11
111 = 3 × 37
112 = 24 × 7
113 = 113
114 = 2 × 3 × 19
115 = 5 × 23
116 = 22 × 29
117 = 32 × 13
118 = 2 × 59
119 = 7 × 17
120 = 23 × 3 × 5
121 = 112
122 = 2 × 61
123 = 3 × 41
124 = 22 × 31
125 = 53
126 = 2 × 32 × 7
127 = 127
128 = 27
129 = 3 × 43
130 = 2 × 5 × 13
131 = 131
132 = 22 × 3 × 11
133 = 7 × 19
134 = 2 × 67
135 = 33 × 5
136 = 23 × 17
137 = 137
138 = 2 × 3 × 23
139 = 139
140 = 22 × 5 × 7
141 = 3 × 47
142 = 2 × 71
143 = 11 × 13
144 = 24 × 32
145 = 5 × 29
146 = 2 × 73
147 = 3 × 72
148 = 22 × 37
149 = 149
150 = 2 × 3 × 52
151 = 151
152 = 23 × 19
153 = 32 × 17
154 = 2 × 7 × 11
155 = 5 × 31
156 = 22 × 3 × 13
157 = 157
158 = 2 × 79
159 = 3 × 53
160 = 25 × 5
161 = 7 × 23
162 = 2 × 34
163 = 163
164 = 22 × 41
165 = 3 × 5 × 11
166 = 2 × 83
167 = 167
168 = 23 × 3 × 7
169 = 132
170 = 2 × 5 × 17
171 = 32 × 19
172 = 22 × 43
173 = 173
174 = 2 × 3 × 29
175 = 52 × 7
176 = 24 × 11
177 = 3 × 59
178 = 2 × 89
179 = 179
180 = 22 × 32 × 5
181 = 181
182 = 2 × 7 × 13
183 = 3 × 61
184 = 23 × 23
185 = 5 × 37
186 = 2 × 3 × 31
187 = 11 × 17
188 = 22 × 47
189 = 33 × 7
190 = 2 × 5 × 19
191 = 191
192 = 26 × 3
193 = 193
194 = 2 × 97
195 = 3 × 5 × 13
196 = 22 × 72
197 = 197
198 = 2 × 32 × 11
199 = 199
200 = 23 × 52
201 = 3 × 67
202 = 2 × 101
203 = 7 × 29
204 = 22 × 3 × 17
205 = 5 × 41
206 = 2 × 103
207 = 32 × 23
208 = 24 × 13
209 = 11 × 19
210 = 2 × 3 × 5 × 7
211 = 211
212 = 22 × 53
213 = 3 × 71
214 = 2 × 107
215 = 5 × 43
216 = 23 × 33
217 = 7 × 31
218 = 2 × 109
219 = 3 × 73
220 = 22 × 5 × 11
221 = 13 × 17
222 = 2 × 3 × 37
223 = 223
224 = 25 × 7
225 = 32 × 52
226 = 2 × 113
227 = 227
228 = 22 × 3 × 19
229 = 229
230 = 2 × 5 × 23
231 = 3 × 7 × 11
232 = 23 × 29
233 = 233
234 = 2 × 32 × 13
235 = 5 × 47
236 = 22 × 59
237 = 3 × 79
238 = 2 × 7 × 17
239 = 239
240 = 24 × 3 × 5
241 = 241
242 = 2 × 112
243 = 35
244 = 22 × 61
245 = 5 × 72
246 = 2 × 3 × 41
247 = 13 × 19
248 = 23 × 31
249 = 3 × 83
250 = 2 × 53
251 = 251
252 = 22 × 32 × 7
253 = 11 × 23
254 = 2 × 127
255 = 3 × 5 × 17
256 = 28
257 = 257
258 = 2 × 3 × 43
259 = 7 × 37
260 = 22 × 5 × 13
261 = 32 × 29
262 = 2 × 131
263 = 263
264 = 23 × 3 × 11
265 = 5 × 53
266 = 2 × 7 × 19
267 = 3 × 89
268 = 22 × 67
269 = 269
270 = 2 × 33 × 5
271 = 271
272 = 24 × 17
273 = 3 × 7 × 13
274 = 2 × 137
275 = 52 × 11
276 = 22 × 3 × 23
277 = 277
278 = 2 × 139
279 = 32 × 31
280 = 23 × 5 × 7
281 = 281
282 = 2 × 3 × 47
283 = 283
284 = 22 × 71
285 = 3 × 5 × 19
286 = 2 × 11 × 13
287 = 7 × 41
288 = 25 × 32
289 = 172
290 = 2 × 5 × 29
291 = 3 × 97
292 = 22 × 73
293 = 293
294 = 2 × 3 × 72
295 = 5 × 59
296 = 23 × 37
297 = 33 × 11
298 = 2 × 149
299 = 13 × 23
300 = 22 × 3 × 52
301 = 7 × 43
302 = 2 × 151
303 = 3 × 101
304 = 24 × 19
305 = 5 × 61
306 = 2 × 32 × 17
307 = 307
308 = 22 × 7 × 11
309 = 3 × 103
310 = 2 × 5 × 31
311 = 311
312 = 23 × 3 × 13
313 = 313
314 = 2 × 157
315 = 32 × 5 × 7
316 = 22 × 79
317 = 317
318 = 2 × 3 × 53
319 = 11 × 29
320 = 26 × 5
321 = 3 × 107
322 = 2 × 7 × 23
323 = 17 × 19
324 = 22 × 34
325 = 52 × 13
326 = 2 × 163
327 = 3 × 109
328 = 23 × 41
329 = 7 × 47
330 = 2 × 3 × 5 × 11
331 = 331
332 = 22 × 83
333 = 32 × 37
334 = 2 × 167
335 = 5 × 67
336 = 24 × 3 × 7
337 = 337
338 = 2 × 132
339 = 3 × 113
340 = 22 × 5 × 17
341 = 11 × 31
342 = 2 × 32 × 19
343 = 73
344 = 23 × 43
345 = 3 × 5 × 23
346 = 2 × 173
347 = 347
348 = 22 × 3 × 29
349 = 349
350 = 2 × 52 × 7
351 = 33 × 13
352 = 25 × 11
353 = 353
354 = 2 × 3 × 59
355 = 5 × 71
356 = 22 × 89
357 = 3 × 7 × 17
358 = 2 × 179
359 = 359
360 = 23 × 32 × 5
361 = 192
362 = 2 × 181
363 = 3 × 112
364 = 22 × 7 × 13
365 = 5 × 73
366 = 2 × 3 × 61
367 = 367
368 = 24 × 23
369 = 32 × 41
370 = 2 × 5 × 37
371 = 7 × 53
372 = 22 × 3 × 31
373 = 373
374 = 2 × 11 × 17
375 = 3 × 53
376 = 23 × 47
377 = 13 × 29
378 = 2 × 33 × 7
379 = 379
380 = 22 × 5 × 19
381 = 3 × 127
382 = 2 × 191
383 = 383
384 = 27 × 3
385 = 5 × 7 × 11
386 = 2 × 193
387 = 32 × 43
388 = 22 × 97
389 = 389
390 = 2 × 3 × 5 × 13
391 = 17 × 23
392 = 23 × 72
393 = 3 × 131
394 = 2 × 197
395 = 5 × 79
396 = 22 × 32 × 11
397 = 397
398 = 2 × 199
399 = 3 × 7 × 19
400 = 24 × 52
401 = 401
402 = 2 × 3 × 67
403 = 13 × 31
404 = 22 × 101
405 = 34 × 5
406 = 2 × 7 × 29
407 = 11 × 37
408 = 23 × 3 × 17
409 = 409
410 = 2 × 5 × 41
411 = 3 × 137
412 = 22 × 103
413 = 7 × 59
414 = 2 × 32 × 23
415 = 5 × 83
416 = 25 × 13
417 = 3 × 139
418 = 2 × 11 × 19
419 = 419
420 = 22 × 3 × 5 × 7
421 = 421
422 = 2 × 211
423 = 32 × 47
424 = 23 × 53
425 = 52 × 17
426 = 2 × 3 × 71
427 = 7 × 61
428 = 22 × 107
429 = 3 × 11 × 13
430 = 2 × 5 × 43
431 = 431
432 = 24 × 33
433 = 433
434 = 2 × 7 × 31
435 = 3 × 5 × 29
436 = 22 × 109
437 = 19 × 23
438 = 2 × 3 × 73
439 = 439
440 = 23 × 5 × 11
441 = 32 × 72
442 = 2 × 13 × 17
443 = 443
444 = 22 × 3 × 37
445 = 5 × 89
446 = 2 × 223
447 = 3 × 149
448 = 26 × 7
449 = 449
450 = 2 × 32 × 52
451 = 11 × 41
452 = 22 × 113
453 = 3 × 151
454 = 2 × 227
455 = 5 × 7 × 13
456 = 23 × 3 × 19
457 = 457
458 = 2 × 229
459 = 33 × 17
460 = 22 × 5 × 23
461 = 461
462 = 2 × 3 × 7 × 11
463 = 463
464 = 24 × 29
465 = 3 × 5 × 31
466 = 2 × 233
467 = 467
468 = 22 × 32 × 13
469 = 7 × 67
470 = 2 × 5 × 47
471 = 3 × 157
472 = 23 × 59
473 = 11 × 43
474 = 2 × 3 × 79
475 = 52 × 19
476 = 22 × 7 × 17
477 = 32 × 53
478 = 2 × 239
479 = 479
480 = 25 × 3 × 5
481 = 13 × 37
482 = 2 × 241
483 = 3 × 7 × 23
484 = 22 × 112
485 = 5 × 97
486 = 2 × 35
487 = 487
488 = 23 × 61
489 = 3 × 163
490 = 2 × 5 × 72
491 = 491
492 = 22 × 3 × 41
493 = 17 × 29
494 = 2 × 13 × 19
495 = 32 × 5 × 11
496 = 24 × 31
497 = 7 × 71
498 = 2 × 3 × 83
499 = 499
500 = 22 × 53
501 = 3 × 167
502 = 2 × 251
503 = 503
504 = 23 × 32 × 7
505 = 5 × 101
506 = 2 × 11 × 23
507 = 3 × 132
508 = 22 × 127
509 = 509
510 = 2 × 3 × 5 × 17
511 = 7 × 73
512 = 29
513 = 33 × 19
514 = 2 × 257
515 = 5 × 103
516 = 22 × 3 × 43
517 = 11 × 47
518 = 2 × 7 × 37
519 = 3 × 173
520 = 23 × 5 × 13
521 = 521
522 = 2 × 32 × 29
523 = 523
524 = 22 × 131
525 = 3 × 52 × 7
526 = 2 × 263
527 = 17 × 31
528 = 24 × 3 × 11
529 = 232
530 = 2 × 5 × 53
531 = 32 × 59
532 = 22 × 7 × 19
533 = 13 × 41
534 = 2 × 3 × 89
535 = 5 × 107
536 = 23 × 67
537 = 3 × 179
538 = 2 × 269
539 = 72 × 11
540 = 22 × 33 × 5
541 = 541
542 = 2 × 271
543 = 3 × 181
544 = 25 × 17
545 = 5 × 109
546 = 2 × 3 × 7 × 13
547 = 547
548 = 22 × 137
549 = 32 × 61
550 = 2 × 52 × 11
551 = 19 × 29
552 = 23 × 3 × 23
553 = 7 × 79
554 = 2 × 277
555 = 3 × 5 × 37
556 = 22 × 139
557 = 557
558 = 2 × 32 × 31
559 = 13 × 43
560 = 24 × 5 × 7
561 = 3 × 11 × 17
562 = 2 × 281
563 = 563
564 = 22 × 3 × 47
565 = 5 × 113
566 = 2 × 283
567 = 34 × 7
568 = 23 × 71
569 = 569
570 = 2 × 3 × 5 × 19
571 = 571
572 = 22 × 11 × 13
573 = 3 × 191
574 = 2 × 7 × 41
575 = 52 × 23
576 = 26 × 32
577 = 577
578 = 2 × 172
579 = 3 × 193
580 = 22 × 5 × 29
581 = 7 × 83
582 = 2 × 3 × 97
583 = 11 × 53
584 = 23 × 73
585 = 32 × 5 × 13
586 = 2 × 293
587 = 587
588 = 22 × 3 × 72
589 = 19 × 31
590 = 2 × 5 × 59
591 = 3 × 197
592 = 24 × 37
593 = 593
594 = 2 × 33 × 11
595 = 5 × 7 × 17
596 = 22 × 149
597 = 3 × 199
598 = 2 × 13 × 23
599 = 599
600 = 23 × 3 × 52
601 = 601
602 = 2 × 7 × 43
603 = 32 × 67
604 = 22 × 151
605 = 5 × 112
606 = 2 × 3 × 101
607 = 607
608 = 25 × 19
609 = 3 × 7 × 29
610 = 2 × 5 × 61
611 = 13 × 47
612 = 22 × 32 × 17
613 = 613
614 = 2 × 307
615 = 3 × 5 × 41
616 = 23 × 7 × 11
617 = 617
618 = 2 × 3 × 103
619 = 619
620 = 22 × 5 × 31
621 = 33 × 23
622 = 2 × 311
623 = 7 × 89
624 = 24 × 3 × 13
625 = 54
626 = 2 × 313
627 = 3 × 11 × 19
628 = 22 × 157
629 = 17 × 37
630 = 2 × 32 × 5 × 7
631 = 631
632 = 23 × 79
633 = 3 × 211
634 = 2 × 317
635 = 5 × 127
636 = 22 × 3 × 53
637 = 72 × 13
638 = 2 × 11 × 29
639 = 32 × 71
640 = 27 × 5
641 = 641
642 = 2 × 3 × 107
643 = 643
644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
647 = 647
648 = 23 × 34
649 = 11 × 59
650 = 2 × 52 × 13
651 = 3 × 7 × 31
652 = 22 × 163
653 = 653
654 = 2 × 3 × 109
655 = 5 × 131
656 = 24 × 41
657 = 32 × 73
658 = 2 × 7 × 47
659 = 659
660 = 22 × 3 × 5 × 11
661 = 661
662 = 2 × 331
663 = 3 × 13 × 17
664 = 23 × 83
665 = 5 × 7 × 19
666 = 2 × 32 × 37
667 = 23 × 29
668 = 22 × 167
669 = 3 × 223
670 = 2 × 5 × 67
671 = 11 × 61
672 = 25 × 3 × 7
673 = 673
674 = 2 × 337
675 = 33 × 52
676 = 22 × 132
677 = 677
678 = 2 × 3 × 113
679 = 7 × 97
680 = 23 × 5 × 17
681 = 3 × 227
682 = 2 × 11 × 31
683 = 683
684 = 22 × 32 × 19
685 = 5 × 137
686 = 2 × 73
687 = 3 × 229
688 = 24 × 43
689 = 13 × 53
690 = 2 × 3 × 5 × 23
691 = 691
692 = 22 × 173
693 = 32 × 7 × 11
694 = 2 × 347
695 = 5 × 139
696 = 23 × 3 × 29
697 = 17 × 41
698 = 2 × 349
699 = 3 × 233
700 = 22 × 52 × 7
701 = 701
702 = 2 × 33 × 13
703 = 19 × 37
704 = 26 × 11
705 = 3 × 5 × 47
706 = 2 × 353
707 = 7 × 101
708 = 22 × 3 × 59
709 = 709
710 = 2 × 5 × 71
711 = 32 × 79
712 = 23 × 89
713 = 23 × 31
714 = 2 × 3 × 7 × 17
715 = 5 × 11 × 13
716 = 22 × 179
717 = 3 × 239
718 = 2 × 359
719 = 719
720 = 24 × 32 × 5
721 = 7 × 103
722 = 2 × 192
723 = 3 × 241
724 = 22 × 181
725 = 52 × 29
726 = 2 × 3 × 112
727 = 727
728 = 23 × 7 × 13
729 = 36
730 = 2 × 5 × 73
731 = 17 × 43
732 = 22 × 3 × 61
733 = 733
734 = 2 × 367
735 = 3 × 5 × 72
736 = 25 × 23
737 = 11 × 67
738 = 2 × 32 × 41
739 = 739
740 = 22 × 5 × 37
741 = 3 × 13 × 19
742 = 2 × 7 × 53
743 = 743
744 = 23 × 3 × 31
745 = 5 × 149
746 = 2 × 373
747 = 32 × 83
748 = 22 × 11 × 17
749 = 7 × 107
750 = 2 × 3 × 53
751 = 751
752 = 24 × 47
753 = 3 × 251
754 = 2 × 13 × 29
755 = 5 × 151
756 = 22 × 33 × 7
757 = 757
758 = 2 × 379
759 = 3 × 11 × 23
760 = 23 × 5 × 19
761 = 761
762 = 2 × 3 × 127
763 = 7 × 109
764 = 22 × 191
765 = 32 × 5 × 17
766 = 2 × 383
767 = 13 × 59
768 = 28 × 3
769 = 769
770 = 2 × 5 × 7 × 11
771 = 3 × 257
772 = 22 × 193
773 = 773
774 = 2 × 32 × 43
775 = 52 × 31
776 = 23 × 97
777 = 3 × 7 × 37
778 = 2 × 389
779 = 19 × 41
780 = 22 × 3 × 5 × 13
781 = 11 × 71
782 = 2 × 17 × 23
783 = 33 × 29
784 = 24 × 72
785 = 5 × 157
786 = 2 × 3 × 131
787 = 787
788 = 22 × 197
789 = 3 × 263
790 = 2 × 5 × 79
791 = 7 × 113
792 = 23 × 32 × 11
793 = 13 × 61
794 = 2 × 397
795 = 3 × 5 × 53
796 = 22 × 199
797 = 797
798 = 2 × 3 × 7 × 19
799 = 17 × 47
800 = 25 × 52
801 = 32 × 89
802 = 2 × 401
803 = 11 × 73
804 = 22 × 3 × 67
805 = 5 × 7 × 23
806 = 2 × 13 × 31
807 = 3 × 269
808 = 23 × 101
809 = 809
810 = 2 × 34 × 5
811 = 811
812 = 22 × 7 × 29
813 = 3 × 271
814 = 2 × 11 × 37
815 = 5 × 163
816 = 24 × 3 × 17
817 = 19 × 43
818 = 2 × 409
819 = 32 × 7 × 13
820 = 22 × 5 × 41
821 = 821
822 = 2 × 3 × 137
823 = 823
824 = 23 × 103
825 = 3 × 52 × 11
826 = 2 × 7 × 59
827 = 827
828 = 22 × 32 × 23
829 = 829
830 = 2 × 5 × 83
831 = 3 × 277
832 = 26 × 13
833 = 72 × 17
834 = 2 × 3 × 139
835 = 5 × 167
836 = 22 × 11 × 19
837 = 33 × 31
838 = 2 × 419
839 = 839
840 = 23 × 3 × 5 × 7
841 = 292
842 = 2 × 421
843 = 3 × 281
844 = 22 × 211
845 = 5 × 132
846 = 2 × 32 × 47
847 = 7 × 112
848 = 24 × 53
849 = 3 × 283
850 = 2 × 52 × 17
851 = 23 × 37
852 = 22 × 3 × 71
853 = 853
854 = 2 × 7 × 61
855 = 32 × 5 × 19
856 = 23 × 107
857 = 857
858 = 2 × 3 × 11 × 13
859 = 859
860 = 22 × 5 × 43
861 = 3 × 7 × 41
862 = 2 × 431
863 = 863
864 = 25 × 33
865 = 5 × 173
866 = 2 × 433
867 = 3 × 172
868 = 22 × 7 × 31
869 = 11 × 79
870 = 2 × 3 × 5 × 29
871 = 13 × 67
872 = 23 × 109
873 = 32 × 97
874 = 2 × 19 × 23
875 = 53 × 7
876 = 22 × 3 × 73
877 = 877
878 = 2 × 439
879 = 3 × 293
880 = 24 × 5 × 11
881 = 881
882 = 2 × 32 × 72
883 = 883
884 = 22 × 13 × 17
885 = 3 × 5 × 59
886 = 2 × 443
887 = 887
888 = 23 × 3 × 37
889 = 7 × 127
890 = 2 × 5 × 89
891 = 34 × 11
892 = 22 × 223
893 = 19 × 47
894 = 2 × 3 × 149
895 = 5 × 179
896 = 27 × 7
897 = 3 × 13 × 23
898 = 2 × 449
899 = 29 × 31
900 = 22 × 32 × 52
901 = 17 × 53
902 = 2 × 11 × 41
903 = 3 × 7 × 43
904 = 23 × 113
905 = 5 × 181
906 = 2 × 3 × 151
907 = 907
908 = 22 × 227
909 = 32 × 101
910 = 2 × 5 × 7 × 13
911 = 911
912 = 24 × 3 × 19
913 = 11 × 83
914 = 2 × 457
915 = 3 × 5 × 61
916 = 22 × 229
917 = 7 × 131
918 = 2 × 33 × 17
919 = 919
920 = 23 × 5 × 23
921 = 3 × 307
922 = 2 × 461
923 = 13 × 71
924 = 22 × 3 × 7 × 11
925 = 52 × 37
926 = 2 × 463
927 = 32 × 103
928 = 25 × 29
929 = 929
930 = 2 × 3 × 5 × 31
931 = 72 × 19
932 = 22 × 233
933 = 3 × 311
934 = 2 × 467
935 = 5 × 11 × 17
936 = 23 × 32 × 13
937 = 937
938 = 2 × 7 × 67
939 = 3 × 313
940 = 22 × 5 × 47
941 = 941
942 = 2 × 3 × 157
943 = 23 × 41
944 = 24 × 59
945 = 33 × 5 × 7
946 = 2 × 11 × 43
947 = 947
948 = 22 × 3 × 79
949 = 13 × 73
950 = 2 × 52 × 19
951 = 3 × 317
952 = 23 × 7 × 17
953 = 953
954 = 2 × 32 × 53
955 = 5 × 191
956 = 22 × 239
957 = 3 × 11 × 29
958 = 2 × 479
959 = 7 × 137
960 = 26 × 3 × 5
961 = 312
962 = 2 × 13 × 37
963 = 32 × 107
964 = 22 × 241
965 = 5 × 193
966 = 2 × 3 × 7 × 23
967 = 967
968 = 23 × 112
969 = 3 × 17 × 19
970 = 2 × 5 × 97
971 = 971
972 = 22 × 35
973 = 7 × 139
974 = 2 × 487
975 = 3 × 52 × 13
976 = 24 × 61
977 = 977
978 = 2 × 3 × 163
979 = 11 × 89
980 = 22 × 5 × 72
981 = 32 × 109
982 = 2 × 491
983 = 983
984 = 23 × 3 × 41
985 = 5 × 197
986 = 2 × 17 × 29
987 = 3 × 7 × 47
988 = 22 × 13 × 19
989 = 23 × 43
990 = 2 × 32 × 5 × 11
991 = 991
992 = 25 × 31
993 = 3 × 331
994 = 2 × 7 × 71
995 = 5 × 199
996 = 22 × 3 × 83
997 = 997
998 = 2 × 499
999 = 33 × 37
1000 = 23 × 53
It is simple to check these results by direct multiplication.
The so-called strong form of Goldbach’s conjecture states that every even number greater than two is the sum of two primes. Other than four, which is two plus two, even numbers can be decomposed into two odd primes, often in multiple ways. It is straightforward with the existing apparatus to check all possible decompositions as to whether both terms are prime or not.
The result for even numbers up to one hundred is
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7
16 = 3 + 13 = 5 + 11
18 = 5 + 13 = 7 + 11
20 = 3 + 17 = 7 + 13
22 = 3 + 19 = 5 + 17 = 11 + 11
24 = 5 + 19 = 7 + 17 = 11 + 13
26 = 3 + 23 = 7 + 19 = 13 + 13
28 = 5 + 23 = 11 + 17
30 = 7 + 23 = 11 + 19 = 13 + 17
32 = 3 + 29 = 13 + 19
34 = 3 + 31 = 5 + 29 = 11 + 23 = 17 + 17
36 = 5 + 31 = 7 + 29 = 13 + 23 = 17 + 19
38 = 7 + 31 = 19 + 19
40 = 3 + 37 = 11 + 29 = 17 + 23
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23
44 = 3 + 41 = 7 + 37 = 13 + 31
46 = 3 + 43 = 5 + 41 = 17 + 29 = 23 + 23
48 = 5 + 43 = 7 + 41 = 11 + 37 = 17 + 31 = 19 + 29
50 = 3 + 47 = 7 + 43 = 13 + 37 = 19 + 31
52 = 5 + 47 = 11 + 41 = 23 + 29
54 = 7 + 47 = 11 + 43 = 13 + 41 = 17 + 37 = 23 + 31
56 = 3 + 53 = 13 + 43 = 19 + 37
58 = 5 + 53 = 11 + 47 = 17 + 41 = 29 + 29
60 = 7 + 53 = 13 + 47 = 17 + 43 = 19 + 41 = 23 + 37 = 29 + 31
62 = 3 + 59 = 19 + 43 = 31 + 31
64 = 3 + 61 = 5 + 59 = 11 + 53 = 17 + 47 = 23 + 41
66 = 5 + 61 = 7 + 59 = 13 + 53 = 19 + 47 = 23 + 43 = 29 + 37
68 = 7 + 61 = 31 + 37
70 = 3 + 67 = 11 + 59 = 17 + 53 = 23 + 47 = 29 + 41
72 = 5 + 67 = 11 + 61 = 13 + 59 = 19 + 53 = 29 + 43 = 31 + 41
74 = 3 + 71 = 7 + 67 = 13 + 61 = 31 + 43 = 37 + 37
76 = 3 + 73 = 5 + 71 = 17 + 59 = 23 + 53 = 29 + 47
78 = 5 + 73 = 7 + 71 = 11 + 67 = 17 + 61 = 19 + 59 = 31 + 47 = 37 + 41
80 = 7 + 73 = 13 + 67 = 19 + 61 = 37 + 43
82 = 3 + 79 = 11 + 71 = 23 + 59 = 29 + 53 = 41 + 41
84 = 5 + 79 = 11 + 73 = 13 + 71 = 17 + 67 = 23 + 61 = 31 + 53 = 37 + 47 = 41 + 43
86 = 3 + 83 = 7 + 79 = 13 + 73 = 19 + 67 = 43 + 43
88 = 5 + 83 = 17 + 71 = 29 + 59 = 41 + 47
90 = 7 + 83 = 11 + 79 = 17 + 73 = 19 + 71 = 23 + 67 = 29 + 61 = 31 + 59 = 37 + 53 = 43 + 47
92 = 3 + 89 = 13 + 79 = 19 + 73 = 31 + 61
94 = 5 + 89 = 11 + 83 = 23 + 71 = 41 + 53 = 47 + 47
96 = 7 + 89 = 13 + 83 = 17 + 79 = 23 + 73 = 29 + 67 = 37 + 59 = 43 + 53
98 = 19 + 79 = 31 + 67 = 37 + 61
100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53
The number of decompositions into primes can be compared to A045917 for accuracy. A related set of integers is A002375 which differs only in the second term.
While there is no apparent pattern to the number of decompositions, one is tempted to ask about the minimum or maximum distance between the primes in each pair. This is not difficult to determine: first the minimum differences, which is A066285,
0, 0, 2, 0, 2, 0, 6, 4, 6, 0, 2, 0, 6, 4, 6, 0, 2, 0, 6, 4, 18, 0, 10, 12, 6, 8, 18, 0, 2, 0, 18, 8, 6, 12, 10, 0, 18, 4, 6, 0, 2, 0, 6, 4, 30, 0, 10, 24, 6
followed by the maximum differences, which is A303603 offset by one term:
0, 0, 2, 4, 2, 8, 10, 8, 14, 16, 14, 20, 18, 16, 26, 28, 26, 24, 34, 32, 38, 40, 38, 44, 42, 40, 50, 48, 46, 56, 58, 56, 54, 64, 62, 68, 70, 68, 66, 76, 74, 80, 78, 76, 86, 84, 82, 60, 94
Unfortunately plots of these two lists of integers reveal no apparent patterns. Schade!
Here is another way to think about Goldbach’s conjecture: if every even number greater than two is the sum of two primes, every integer greater than one is the average of two primes. This means
2n=p1+p2→n=p1+p22→n±Δ=(p1,p2)
It is interesting to tabulate the values Δ(n) for each integer:
Δ(2) = [ 0 ]
Δ(3) = [ 0 ]
Δ(4) = [ 1 ]
Δ(5) = [ 0, 2 ]
Δ(6) = [ 1 ]
Δ(7) = [ 0, 4 ]
Δ(8) = [ 3, 5 ]
Δ(9) = [ 2, 4 ]
Δ(10) = [ 3, 7 ]
Δ(11) = [ 0, 6, 8 ]
Δ(12) = [ 1, 5, 7 ]
Δ(13) = [ 0, 6, 10 ]
Δ(14) = [ 3, 9 ]
Δ(15) = [ 2, 4, 8 ]
Δ(16) = [ 3, 13 ]
Δ(17) = [ 0, 6, 12, 14 ]
Δ(18) = [ 1, 5, 11, 13 ]
Δ(19) = [ 0, 12 ]
Δ(20) = [ 3, 9, 17 ]
Δ(21) = [ 2, 8, 10, 16 ]
Δ(22) = [ 9, 15, 19 ]
Δ(23) = [ 0, 6, 18, 20 ]
Δ(24) = [ 5, 7, 13, 17, 19 ]
Δ(25) = [ 6, 12, 18, 22 ]
Δ(26) = [ 3, 15, 21 ]
Δ(27) = [ 4, 10, 14, 16, 20 ]
Δ(28) = [ 9, 15, 25 ]
Δ(29) = [ 0, 12, 18, 24 ]
Δ(30) = [ 1, 7, 11, 13, 17, 23 ]
Δ(31) = [ 0, 12, 28 ]
Δ(32) = [ 9, 15, 21, 27, 29 ]
Δ(33) = [ 4, 10, 14, 20, 26, 28 ]
Δ(34) = [ 3, 27 ]
Δ(35) = [ 6, 12, 18, 24, 32 ]
Δ(36) = [ 5, 7, 17, 23, 25, 31 ]
Δ(37) = [ 0, 6, 24, 30, 34 ]
Δ(38) = [ 9, 15, 21, 33, 35 ]
Δ(39) = [ 2, 8, 20, 22, 28, 32, 34 ]
Δ(40) = [ 3, 21, 27, 33 ]
Δ(41) = [ 0, 12, 18, 30, 38 ]
Δ(42) = [ 1, 5, 11, 19, 25, 29, 31, 37 ]
Δ(43) = [ 0, 24, 30, 36, 40 ]
Δ(44) = [ 3, 15, 27, 39 ]
Δ(45) = [ 2, 8, 14, 16, 22, 26, 28, 34, 38 ]
Δ(46) = [ 15, 27, 33, 43 ]
Δ(47) = [ 0, 6, 24, 36, 42 ]
Δ(48) = [ 5, 11, 19, 25, 31, 35, 41 ]
Δ(49) = [ 12, 18, 30 ]
Δ(50) = [ 3, 9, 21, 33, 39, 47 ]
Curiouser and curiouser...
A pair of primes are twin if they differ by two. These too are simple to determine with existing apparatus:
(3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), (101,103), (107,109), (137,139), (149,151), (179,181), (191,193), (197,199), (227,229), (239,241), (269,271), (281,283), (311,313), (347,349), (419,421), (431,433), (461,463), (521,523), (569,571), (599,601), (617,619), (641,643), (659,661), (809,811), (821,823), (827,829), (857,859), (881,883)
Without the parentheses this is A077800. Other than the first pair, the even integer centered between the twins is
6, 12, 18, 30, 42, 60, 72, 102, 108, 138, 150, 180, 192, 198, 228, 240, 270, 282, 312, 348, 420, 432, 462, 522, 570, 600, 618, 642, 660, 810, 822, 828, 858, 882
Since these integers occur in a string of three numbers, where the first and last are prime, they must also be divisible by three. Dividing the set by six gives
1, 2, 3, 5, 7, 10, 12, 17, 18, 23, 25, 30, 32, 33, 38, 40, 45, 47, 52, 58, 70, 72, 77, 87, 95, 100, 103, 107, 110, 135, 137, 138, 143, 147
which prompts one to ask about the differences between these integers:
1, 1, 2, 2, 3, 2, 5, 1, 5, 2, 5, 2, 1, 5, 2, 5, 2, 5, 6, 12, 2, 5, 10, 8, 5, 3, 4, 3, 25, 2, 1, 5, 4
Unfortunately this has no discernible pattern. Schade!
How about non-twin primes? These are the integers
23, 37, 47, 53, 67, 79, 83, 89, 97, 113, 127, 131, 157, 163, 167, 173, 211, 223, 233, 251, 257, 263, 277, 293, 307, 317, 331, 337, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 439, 443, 449, 457, 467, 479, 487, 491, 499, 503, 509, 541, 547, 557, 563, 577, 587, 593, 607, 613, 631, 647, 653, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 839, 853, 863, 877, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
These integers are also adjacent to a number divisible by six, but before or after? Taking the appropriate modulus and adjusting to plus or minus one gives
-1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, -1, -1, 1, -1, -1, -1, 1, 1
with again no discernible pattern. Doppelt schade!
Uploaded 2023.04.23 analyticphysics.com